package com.hyper_yang.algorithmRecord;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

// 只出现一次的数字
public class LeetCode_136 {
    // ArrayList
    public static int singleNumber1(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (Integer num : nums) { // int 是基本数据类型，会调用remove(index)
            if (list.contains(num)) list.remove(num); // 这里要按元素，移除remove(object)
            else list.add(num);
        }
        return list.get(0);
    }

    // hashMap
    public static int singleNumber2(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.get(num) != null) map.remove(num);
            else map.put(num, 1);
        }
        return map.keySet().iterator().next();
    }

    // hashSet
    public static int singleNumber3(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int arraySum = 0;
        int setSum = 0;
        for (int num : nums) {
            set.add(num);
            arraySum += num;
        }
        for (int i : set) {
            setSum += i;
        }
        return 2 * setSum - arraySum;
    }

    // 异或 ^   a ^ a = 0; a ^ 0 = a;
    public static int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

    public static void main(String[] args) {
        long l = System.currentTimeMillis();

        System.out.println(singleNumber(new int[]{2, 2, 1}));
        System.out.println(singleNumber(new int[]{4, 1, 2, 1, 2}));
        System.out.println(singleNumber(new int[]{1}));

        long l1 = System.currentTimeMillis();
        System.out.println("t: " + (l1 - l));
    }
}
